package fun.ticsmyc.question;

import fun.ticsmyc.tools.ListNode;

import java.util.PriorityQueue;

/**
 * 23. 合并K个升序链表
 * 优先队列大法好
 * @author Ticsmyc
 * @package fun.ticsmyc.dataStructure
 * @date 2021-02-04 17:53
 */
public class 合并k个升序链表 {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = new ListNode(-1);
        ListNode cur = res;

        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b)->a.val-b.val);

        for(int i=0;i<lists.length;++i){
            if(lists[i]!= null){
                queue.add(lists[i]);
            }
        }
        while(!queue.isEmpty()){
            ListNode tmp = queue.poll();
            if(tmp.next != null){
                queue.add(tmp.next);
            }
            cur.next = tmp;
            cur=cur.next;
        }
        return res.next;
    }
}
